/*
 * @lc app=leetcode.cn id=151 lang=cpp
 * @lcpr version=30204
 *
 * [151] 反转字符串中的单词
 */

// @lcpr-template-start
using namespace std;
#include <algorithm>
#include <array>
#include <bitset>
#include <climits>
#include <deque>
#include <functional>
#include <iostream>
#include <list>
#include <queue>
#include <stack>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
// @lcpr-template-end
// @lc code=start
class Solution
{
public:
    string reverseWords(string s)
    {
        if (s.empty())
            return s;
        // 去除首尾空格
        int start = 0, end = s.size() - 1;
        while (start <= end && s[start] == ' ')
            start++;
        while (end >= start && s[end] == ' ')
            end--;
        // 去除中间多余空格
        string result;
        while (start <= end)
        {
            if (s[start] != ' ')
            {
                result += s[start];
            }
            else
            {
                if (result.back() != ' ')
                {
                    result += ' ';
                }
            }
            start++;
        }
        // 反转字符串
        reverse(result.begin(), result.end());
        // 反转每个单词
        int wordStart = 0;
        for (int i = 0; i <= result.size(); i++)
        {
            if (i == result.size() || result[i] == ' ')
            {
                reverse(result.begin() + wordStart, result.begin() + i);
                wordStart = i + 1;
            }
        }
        return result;
    }
};
// @lc code=end

/*
// @lcpr case=start
// "the sky is blue"\n
// @lcpr case=end

// @lcpr case=start
// "  hello world  "\n
// @lcpr case=end

// @lcpr case=start
// "a good   example"\n
// @lcpr case=end

 */
